package _动态规划;

import java.util.Arrays;

public class bb {
    // 完全背包：方案数（正序遍历）：https://leetcode.cn/problems/coin-change-ii/
    // 518：完全背包 + 计数型	零钱兑换（无限次用）
    public int change(int amount, int[] coins) {
        // dp[j] 表示：凑成金额 j 的组合数
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

    // 322：零钱兑换：最少的硬币个数 ；完全背包：最值问题：https://leetcode.cn/problems/coin-change/
    public int coinChange(int[] coins, int amount) {
        // dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    //  01 背包问题：想办法把原问题转化为背包问题
    //  先遍历物品、再遍历背包；背包从大到小遍历
    //  每一道题：关键看dp的定义、递推公式、dp初始化

    // AcWing 2. 01 背包问题
    public int knapsack(int[] v, int[] w, int V) {
        int n = v.length;
        int[] dp = new int[V + 1];

        for (int i = 0; i < n; i++) {
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }

        return dp[V];
    }

    //  416：分割等和子集  https://leetcode.cn/problems/partition-equal-subset-sum/
    //  dp[j] = true/false 表示是否存在一个子集，和正好为 j
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums)
            sum += num;

        if (sum % 2 != 0)
            return false;
        int target = sum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] |= dp[j - num];
            }
        }

        return dp[target];
    }


    // 494：目标和：https://leetcode.cn/problems/target-sum/
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum += num;

        if (Math.abs(target) > sum || (target + sum) % 2 != 0)
            return 0;

        int bagSize = (target + sum) / 2;
        // dp[i] = 和为 i 的子集有多少种（方案总数）
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;

        for (int num : nums) {
            for (int j = bagSize; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[bagSize];
    }

    // 1049 — 最后一块石头的重量 II: https://leetcode.cn/problems/last-stone-weight-ii/description/
    // 不要模拟问题。而是转化问题：把所有石头分成两堆，使得这两堆石头重量之差尽量小。
    // 所以我们目标是：找到一组子集，使它的总和尽量接近 sum / 2

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones)
            sum += stone;
        int target = sum / 2;

        // dp[j] = 总和不超过 j 的最大子集和
        int[] dp = new int[target + 1];

        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }

        return sum - 2 * dp[target]; // 另一堆是 sum - dp[target]
    }

    /*1981:最小化目标与选择元素的差：   https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/
           你有一个 m x n 的二维数组 mat，每一行可以选一个数。最终你将选出 m 个数（每行一个）。
           问：你选出的这些数之和，与给定的 target 的绝对差值最小是多少？
           每一行可以看成一层，选择其中一个元素，相当于「从多个物品中选择一个加入背包」

                dp[i][j] = 前 i 行中，每行选一个数，总和为 j 是否可达（true/false）（分层背包）
                最终，我们遍历所有合法的 j，计算 |j - target| 最小的那个
                dp[i][j] |= dp[i - 1][j - mat[i][k]];
    */
    public int minimizeTheDifference(int[][] mat, int target) {
        int m = mat.length, n = mat[0].length;
        int maxSum = m * 70; // 每个数字 <= 70，总最多 m*70

        boolean[] dp = new boolean[maxSum + 1];
        for (int num : mat[0])
            dp[num] = true;

        for (int i = 1; i < m; i++) {                // 第 i 行
            boolean[] next = new boolean[maxSum + 1];

            for (int j = 0; j <= maxSum; j++) {      // 当前总和 j （从旧的dp中获取）
                if (!dp[j]) continue;       // 如果上一轮都凑不出dp[j]
                for (int num : mat[i]) {
                    if (j + num <= maxSum) {         // 当前的选择
                        next[j + num] = true;
                    }
                }
            }
            dp = next;
        }

        int res = Integer.MAX_VALUE;
        for (int sum = 0; sum <= maxSum; sum++) {
            if (dp[sum]) {
                res = Math.min(res, Math.abs(sum - target));
            }
        }
        return res;
    }

    // 474 ：一和零（二维 0-1 背包）
    /*
    *   给定一个 01 字符串数组 strs 和两个整数 m 和 n：
        表示你最多有 m 个 0 和 n 个 1。
        请找出最多能拼出的子集个数，使这些子集中的字符串所用的 0 和 1 总数不超过 m 和 n
    * */
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j] 表示使用 i 个 0、 j 个 1，最多能组成多少个字符串
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zero = 0, one = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zero++;
                else one++;
            }

            for (int i = m; i >= zero; i--) {
                for (int j = n; j >= one; j--) {
                    // dp[i][j] = max(当前不选, 选这个字符串后的 dp[i - 0数][j - 1数] + 1)

                    dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
                }
            }
        }
        return dp[m][n];
    }


//    目标	            正确遍历顺序
//    组合数（顺序无关）	外物品 coin，内容量 j  （先物品再背包）
//    排列数（顺序敏感）	外容量 j，内物品 coin

    // 377 ：组合总数IV ：https://leetcode.cn/problems/combination-sum-iv/description/
    // 顺序不同的序列被视作不同的组合。
    // 完全背包 + 计数 + 顺序敏感
    public int combinationSum4(int[] nums, int target) {
        //  dp[i] = 和为 i 的所有排列数（顺序不同算不同）
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

    // 1155. 掷骰子等于目标和的方法数 ：https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/description/
    // 同 1981
    // description：给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果，使得骰子面朝上的数字总和等于 target
    // 完全背包（分层） + 计数 + 顺序敏感
    public int numRollsToTarget(int n, int k, int target) {
        int MOD = 1_000_000_007;
        // dp[i] = 和为 i 的方案总数
        int[] dp = new int[target + 1];
        dp[0] = 1;

        // 每一轮的for循环都在做什么事情
        for (int i = 0; i < n; i++) {                                 // 第 i 个筛子
            int[] next = new int[target + 1];

            for (int j = 0; j < target; j++) {                        // 当前总和 j（从旧 dp 枚举）
                if (dp[j] == 0) continue;           //如果当前状态都无法到达
                for (int l = 1; l <= k && j + l <= target; l++) {     //当前筛子可以抛出的面额
                    next[j + l] = (next[j + l] + dp[j]) % MOD;
                }
            }
            dp = next;
        }
        return dp[target];
    }


}














